package lc279;

import java.util.Arrays;

public class Lc279_test {

    /**
     * dp 时间复杂度优化
     * 在1解中，有重复的计算，所以可以通过缓存计算后的值进行时间复杂度优化
     * 这里可以定义一个HashMap，也可以定义一个数组，如果定义数组的话，要注意两个地方
     * 1、注意初始化容量，因为数组是下标是从0开始的，如果我们需要用到n做下标，则需要size=n+1防止溢出
     * 2、数组的值填充需要定义一个不会计算得到的值，不然无法区分这个值到底是计算出来的，还是原来的值。例如这里计算得到的count,永远不可能小于0，
     * 那数组的初始化值就可以是负数，但是尽量不要用-1.为了防止某些题目base case会得到-1的情况。
     * time：O(n*√n)
     * space: O(n)
     * spend: 60m
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        return numSquaresHelper(n, dp);

    }

    private int numSquaresHelper(int n, int[] dp) {
        if(dp[n] != Integer.MIN_VALUE){
            return dp[n];
        }
        if(n == 0){
            return 0;
        }
        int count = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            count = Math.min(count, numSquaresHelper(n - i * i, dp) + 1);

        }
        dp[n] = count;
        return count;
    }

}
